/*
 * @lc app=leetcode.cn id=87 lang=java
 *
 * [87] 扰乱字符串
 */

// @lc code=start
class IsScramble {
  String s1;
  String s2;
  int n;
  int[][][] cache;
  int N = -1, Y = 1, EMPTY = 0;

  public boolean isScramble(String _s1, String _s2) {
    s1 = _s1;
    s2 = _s2;
    if (s1.equals(s2))
      return true;
    if (s1.length() != s2.length())
      return false;
    n = s1.length();
    // cache 的默认值是 EMPTY
    cache = new int[n][n][n + 1];
    return dfs(0, 0, n);
  }

  boolean dfs(int i, int j, int len) {
    if (cache[i][j][len] != EMPTY)
      return cache[i][j][len] == Y;
    String a = s1.substring(i, i + len), b = s2.substring(j, j + len);
    if (a.equals(b)) {
      cache[i][j][len] = Y;
      return true;
    }
    if (!check(a, b)) {
      cache[i][j][len] = N;
      return false;
    }
    for (int k = 1; k < len; k++) {
      // 对应了「s1 的 [0,i) & [i,n)」匹配「s2 的 [0,i) & [i,n)」
      if (dfs(i, j, k) && dfs(i + k, j + k, len - k)) {
        cache[i][j][len] = Y;
        return true;
      }
      // 对应了「s1 的 [0,i) & [i,n)」匹配「s2 的 [n-i,n) & [0,n-i)」
      if (dfs(i, j + len - k, k) && dfs(i + k, j, len - k)) {
        cache[i][j][len] = Y;
        return true;
      }
    }
    cache[i][j][len] = N;
    return false;
  }

  // 检查 s1 和 s2 词频是否相同
  boolean check(String s1, String s2) {
    if (s1.length() != s2.length())
      return false;
    int n = s1.length();
    int[] cnt1 = new int[26], cnt2 = new int[26];
    char[] cs1 = s1.toCharArray(), cs2 = s2.toCharArray();
    for (int i = 0; i < n; i++) {
      cnt1[cs1[i] - 'a']++;
      cnt2[cs2[i] - 'a']++;
    }
    for (int i = 0; i < 26; i++) {
      if (cnt1[i] != cnt2[i])
        return false;
    }
    return true;
  }
}
// @lc code=end
